package app_demo.messageQueue;

import java.util.HashMap;
import java.util.LinkedList;

/**
 * @Description 莉莉丝笔试 设计一个可靠的消息队列
 * @Author Firenut
 * @Date 2023-07-06 12:13
 */
public class MessageQueueDemo {
    // 时间复杂度O(n)，空间复杂度O(n)，其中获取队首消息、获取指定类型的消息、添加消息单次操作的时间复杂度都是O(1)。
    // 消息队列设计思想：使用一个双端队列messageQueue存放消息，再使用一个哈希表将指定类型消息串联起来，键为消息类型，值为队列。
    // 添加消息：将消息添加到messageQueue，同时添加也添加到哈希表中的特定队列中。由于存的都是引用变量，所以每个消息并没有占两份内存。
    // 获取消息：
    //（1）当消息类型为0，也就是获取messgeQueue队首的消息时，将消息类型置为队首消息的类型；此时获队首消息转换成了获取特定类型的第一个消息。
    //（1）获取指定类型的消息。从哈希表中取出消息体，然后维护好messageQueue双端队列。


}

// 宏观上,所有结点的插入都是基于 head 和 tail
// hash表中存放的是不同类型及对应的链表,这个链表和前面head、tail不是同一个链表;
// 不同类型可以理解为是不同的分区
// LinkedList相当于一个双向队列
// 但是结点都是用的同一份引用,所以并没有占用两份内存
class MessageQueue{
    HashMap<Integer, LinkedList<Entity>> hashMap = new HashMap<>();
    Entity head, tail;

    // 获取消息并从队列中移除
    public String get(int type) {
        if (type == 0) {
            if (head == null) {
                return "-1";
            }
            type = head.type;
        }
        if (!hashMap.containsKey(type)) {
            return "-1";
        }

        // 找到type找到hash表中对应的链表，删除该结点entity
        LinkedList<Entity> list = hashMap.get(type);
        Entity entity = list.removeFirst();
        if (list.isEmpty()) {
            hashMap.remove(type);
        }

        // 另外需要在head、tail所在链表中找到该结点,也将其移除
        if (head == entity && tail == entity) {
            head = tail = null;
        } else if (head == entity) {
            removeHead();
        } else if (entity == tail) {
            removeTail();
        } else {
            entity.pre.next = entity.next;
            entity.next.pre = entity.pre;
        }
        return entity.message;
    }

    public void put(int type, String value) {
        Entity entity = new Entity(type, value);
        if (tail == null) {
            head = tail = entity;
        } else {
            entity.pre = tail;
            tail.next = entity;
            tail = entity;
        }
        // 将结点添加到指定类型的链表中,如果不存在,则创建一个新的链表;如果存在则返回该链表
        LinkedList<Entity> list = hashMap.computeIfAbsent(type, k->new LinkedList<>());
        // 将结点插入该链表中
        list.add(entity);
    }

    private void removeHead() {
        if (head == tail) {
            head = tail = null;
        } else {
            head = head.next;
            head.pre = null;
        }
    }

    private void removeTail() {
        if (head == tail) {
            head = tail = null;
        } else {
            tail = tail.pre;
            tail.next = null;
        }
    }

    // 双向链表
    private static class Entity {
        int type;
        String message;
        Entity pre;
        Entity next;

        public Entity(int type, String message) {
            this.type = type;
            this.message = message;
        }
    }
}